package leetcode.pre100;

import leetcode.pre50.Code45_JumpGame2;

/**
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 判断你是否能够到达最后一个位置。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,3,1,1,4]
 * <p>输出: true
 * <p>解释: 我们可以先跳 1 步，从位置 0 到达 位置 1,
 * 然后再从位置 1 跳 3 步到达最后一个位置。
 * <p>
 * 示例 2:
 * <p>
 * <p>输入: [3,2,1,0,4]
 * <p>输出: false
 * 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，
 * 所以你永远不可能到达最后一个位置。
 * <p>
 * <p>
 * 进阶看{@link Code45_JumpGame2}
 * <p>
 * 动态规划见
 * {@link leetcode.a_总结分布.Code01_DP}
 *
 * @since 2019/11/30 0030 下午 9:34
 */
public class Code55_JumpGame {
    /**
     * 方式1：暴力回溯。对当前位置每个都跳，递归下去
     */
    public static boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1) return true;
        return doJump(nums, 0);
    }

    private static boolean doJump(int[] nums, int i) {
        if (i >= nums.length - 1) return true;
        //从当前位置开始能跳跃的最大步数
        int maxStep = Math.min(nums[i], nums.length - 1 - nums[i]);
        for (int j = i + 1; j <= maxStep; j++) {
            if (doJump(nums, j)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 记忆性回溯。memo[i]表示位于i位置是否能跳到最后一个格子
     *
     * @param nums
     * @return
     */
    public static boolean canJump2(int[] nums) {
        if (nums == null || nums.length <= 1) return true;
        //-1 0 1 分别表示不能，未知，能
        int[] memo = new int[nums.length];
        memo[nums.length - 1] = 1;
        return doJump(nums, 0, memo);
    }

    private static boolean doJump(int[] nums, int i, int[] memo) {
        if (i >= nums.length - 1) {
            return true;
        }
        if (memo[i] != 0) return memo[i] == 1;
        //从当前位置开始能跳跃的最大步数
        int maxStep = Math.min(nums[i], nums.length - 1 - i);
        for (int j = i + 1; j <= i + maxStep; j++) {
            if (doJump(nums, j, memo)) {
                //从i位置，j位置都能达到
                memo[i] = memo[j] = 1;
                return true;
            }
        }
        memo[i] = -1;
        return false;
    }

    /**
     * 方式3：dp。dp[i]表示从i位置能否跳到最后
     */
    public static boolean canJump3(int[] nums) {
        if (nums == null || nums.length <= 1) return true;
        boolean[] dp = new boolean[nums.length];
        dp[nums.length - 1] = true;
        for (int i = nums.length - 2; i >= 0; i--) {
            int maxStep = Math.min(nums[i], nums.length - 1 - i);
            //当前位置依赖于从1-maxStep位置.
            for (int j = i + 1; j <= i + maxStep; j++) {
                if (dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }

    /**
     * 方式4：贪心。
     */
    public static boolean canJump4(int[] nums) {
        if (nums == null || nums.length <= 1) return true;
        //最近可达点。最后一个位置可达
        int lastPosition = nums.length - 1;
        //从后往前遍历
        for (int i = nums.length - 2; i >= 0; i--) {
            //当前位置能够达到可达点，那么当前位置作为可达点。
            if (i + nums[i] >= lastPosition) {
                lastPosition = i;
            }
        }
        return lastPosition == 0;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 1, 4};
        System.out.println(canJump4(arr));
    }

}
